home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / yacc.arc / Y4.C < prev    next >
Encoding:
C/C++ Source or Header  |  1985-09-04  |  6.4 KB  |  348 lines
  1. #include "c:dextern"
  2.  
  3. #define a amem
  4. #define mem mem0
  5. #define pa indgo
  6. #define yypact temp1
  7. #define greed tystate
  8.  
  9. int * ggreed = lkst[0].lset;
  10. int * pgo = wsets[0].ws.lset;
  11. int *yypgo = &nontrst[0].tvalue;
  12.  
  13. int maxspr = 0;  /* maximum spread of any entry */
  14. int maxoff = 0;  /* maximum offset into a array */
  15. int *pmem = mem;
  16. int *maxa;
  17. #define NOMORE -1000
  18.  
  19. int nxdb = 0;
  20. int adb = 0;
  21.  
  22. callopt(){
  23.  
  24.     register i, *p, j, k, *q;
  25.  
  26.     /* read the arrays from tempfile and set parameters */
  27.  
  28.     if( (finput=fopen(TEMPNAME,"r")) == NULL ) error( "optimizer cannot open tempfile" );
  29.  
  30.     pgo[0] = 0;
  31.     yypact[0] = 0;
  32.     nstate = 0;
  33.     nnonter = 0;
  34.     for(;;){
  35.         switch( gtnm() ){
  36.  
  37.         case '\n':
  38.             yypact[++nstate] = (--pmem) - mem;
  39.         case ',':
  40.             continue;
  41.  
  42.         case '$':
  43.             break;
  44.  
  45.         default:
  46.             error( "bad tempfile" );
  47.             }
  48.         break;
  49.         }
  50.  
  51.     yypact[nstate] = yypgo[0] = (--pmem) - mem;
  52.  
  53.     for(;;){
  54.         switch( gtnm() ){
  55.  
  56.         case '\n':
  57.             yypgo[++nnonter]= pmem-mem;
  58.         case ',':
  59.             continue;
  60.  
  61.         case EOF:
  62.             break;
  63.  
  64.         default:
  65.             error( "bad tempfile" );
  66.             }
  67.         break;
  68.         }
  69.  
  70.     yypgo[nnonter--] = (--pmem) - mem;
  71.  
  72.  
  73.  
  74.     for( i=0; i<nstate; ++i ){
  75.  
  76.         k = 32000;
  77.         j = 0;
  78.         q = mem + yypact[i+1];
  79.         for( p = mem + yypact[i]; p<q ; p += 2 ){
  80.             if( *p > j ) j = *p;
  81.             if( *p < k ) k = *p;
  82.             }
  83.         if( k <= j ){ /* nontrivial situation */
  84.             /* temporarily, kill this for compatibility
  85.             j -= k;  /* j is now the range */
  86.             if( k > maxoff ) maxoff = k;
  87.             }
  88.         greed[i] = (yypact[i+1]-yypact[i]) + 2*j;
  89.         if( j > maxspr ) maxspr = j;
  90.         }
  91.  
  92.     /* initialize ggreed table */
  93.  
  94.     for( i=1; i<=nnonter; ++i ){
  95.         ggreed[i] = 1;
  96.         j = 0;
  97.         /* minimum entry index is always 0 */
  98.         q = mem + yypgo[i+1] -1;
  99.         for( p = mem+yypgo[i]; p<q ; p += 2 ) {
  100.             ggreed[i] += 2;
  101.             if( *p > j ) j = *p;
  102.             }
  103.         ggreed[i] = ggreed[i] + 2*j;
  104.         if( j > maxoff ) maxoff = j;
  105.         }
  106.  
  107.  
  108.     /* now, prepare to put the shift actions into the a array */
  109.  
  110.     for( i=0; i<ACTSIZE; ++i ) a[i] = 0;
  111.     maxa = a;
  112.  
  113.     for( i=0; i<nstate; ++i ) {
  114.         if( greed[i]==0 && adb>1 ) fprintf( ftable, "State %d: null\n", i );
  115.         pa[i] = YYFLAG1;
  116.         }
  117.  
  118.     while( (i = nxti()) != NOMORE ) {
  119.         if( i >= 0 ) stin(i);
  120.         else gin(-i);
  121.  
  122.         }
  123.  
  124.     if( adb>2 ){ /* print a array */
  125.         for( p=a; p <= maxa; p += 10){
  126.             fprintf( ftable, "%4d  ", p-a );
  127.             for( i=0; i<10; ++i ) fprintf( ftable, "%4d  ", p[i] );
  128.             fprintf( ftable, "\n" );
  129.             }
  130.         }
  131.     /* write out the output appropriate to the language */
  132.  
  133.     aoutput();
  134.  
  135.     osummary();
  136.     ZAPFILE(TEMPNAME);
  137.     }
  138.  
  139. gin(i){
  140.  
  141.     register *p, *r, *s, *q1, *q2;
  142.  
  143.     /* enter gotos on nonterminal i into array a */
  144.  
  145.     ggreed[i] = 0;
  146.  
  147.     q2 = mem+ yypgo[i+1] - 1;
  148.     q1 = mem + yypgo[i];
  149.  
  150.     /* now, find a place for it */
  151.  
  152.     for( p=a; p < &a[ACTSIZE]; ++p ){
  153.         if( *p ) continue;
  154.         for( r=q1; r<q2; r+=2 ){
  155.             s = p + *r +1;
  156.             if( *s ) goto nextgp;
  157.             if( s > maxa ){
  158.                 if( (maxa=s) > &a[ACTSIZE] ) error( "a array overflow" );
  159.                 }
  160.             }
  161.         /* we have found a spot */
  162.  
  163.         *p = *q2;
  164.         if( p > maxa ){
  165.             if( (maxa=p) > &a[ACTSIZE] ) error( "a array overflow" );
  166.             }
  167.         for( r=q1; r<q2; r+=2 ){
  168.             s = p + *r + 1;
  169.             *s = r[1];
  170.             }
  171.  
  172.         pgo[i] = p-a;
  173.         if( adb>1 ) fprintf( ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i] );
  174.         goto nextgi;
  175.  
  176.         nextgp:  ;
  177.         }
  178.  
  179.     error( "cannot place goto %d\n", i );
  180.  
  181.     nextgi:  ;
  182.     }
  183.  
  184. stin(i){
  185.     register *r, *s, n, flag, j, *q1, *q2;
  186.  
  187.     greed[i] = 0;
  188.  
  189.     /* enter state i into the a array */
  190.  
  191.     q2 = mem+yypact[i+1];
  192.     q1 = mem+yypact[i];
  193.     /* find an acceptable place */
  194.  
  195.     for( n= -maxoff; n<ACTSIZE; ++n ){
  196.  
  197.         flag = 0;
  198.         for( r = q1; r < q2; r += 2 ){
  199.             if( (s = *r + n + a ) < a ) goto nextn;
  200.             if( *s == 0 ) ++flag;
  201.             else if( *s != r[1] ) goto nextn;
  202.             }
  203.  
  204.         /* check that the position equals another only if the states are
  205.  identical */
  206.  
  207.         for( j=0; j<nstate; ++j ){
  208.             if( pa[j] == n ) {
  209.                 if( flag ) goto nextn;  /* we have some disagreement */
  210.                 if( yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1] ){
  211.                     /* states are equal */
  212.                     pa[i] = n;
  213.                     if( adb>1 ) fprintf( ftable, "State %d: entry at %d equals state %d\n",
  214.                         i, n, j );
  215.                     return;
  216.                     }
  217.                 goto nextn;  /* we have some disagreement */
  218.                 }
  219.             }
  220.  
  221.         for( r = q1; r < q2; r += 2 ){
  222.             if( (s = *r + n + a ) >= &a[ACTSIZE] ) error( "out of space in optimizer a array" );
  223.             if( s > maxa ) maxa = s;
  224.             if( *s != 0 && *s != r[1] ) error( "clobber of a array, pos'n %d, by %d", s-a, r[1] );
  225.             *s = r[1];
  226.             }
  227.         pa[i] = n;
  228.         if( adb>1 ) fprintf( ftable, "State %d: entry at %d\n", i, pa[i] );
  229.         return;
  230.  
  231.         nextn:  ;
  232.         }
  233.  
  234.     error( "Error; failure to place state %d\n", i );
  235.  
  236.     }
  237.  
  238. nxti(){ /* finds the next i */
  239.     register i, max, maxi;
  240.  
  241.     max = 0;
  242.  
  243.     for( i=1; i<= nnonter; ++i ) if( ggreed[i] >= max ){
  244.         max = ggreed[i];
  245.         maxi = -i;
  246.         }
  247.  
  248.     for( i=0; i<nstate; ++i ) if( greed[i] >= max ){
  249.         max = greed[i];
  250.         maxi = i;
  251.         }
  252.  
  253.     if( nxdb ) fprintf( ftable, "nxti = %d, max = %d\n", maxi, max );
  254.     if( max==0 ) return( NOMORE );
  255.     else return( maxi );
  256.     }
  257.  
  258. osummary(){
  259.     /* write summary */
  260.  
  261.     register i, *p;
  262.  
  263.     if( foutput == NULL ) return;
  264.     i=0;
  265.     for( p=maxa; p>=a; --p ) {
  266.         if( *p == 0 ) ++i;
  267.         }
  268.  
  269.     fprintf( foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
  270.         pmem-mem+1, MEMSIZE, maxa-a+1, ACTSIZE );
  271.     fprintf( foutput, "%d table entries, %d zero\n", (maxa-a)+1, i );
  272.     fprintf( foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff );
  273.  
  274.     }
  275.  
  276. aoutput(){ /* this version is for C */
  277.  
  278.  
  279.     /* write out the optimized parser */
  280.  
  281.     fprintf( ftable, "# define YYLAST %d\n", maxa-a+1 );
  282.  
  283.     arout( "yyact", a, (maxa-a)+1 );
  284.     arout( "yypact", pa, nstate );
  285.     arout( "yypgo", pgo, nnonter+1 );
  286.  
  287.     }
  288.  
  289. arout( s, v, n ) char *s; int *v, n; {
  290.  
  291.     register i;
  292.  
  293.     fprintf( ftable, "short %s[]={\n", s );
  294.     for( i=0; i<n; ){
  295.         if( i%10 == 0 ) fprintf( ftable, "\n" );
  296.         fprintf( ftable, "%4d", v[i] );
  297.         if( ++i == n ) fprintf( ftable, " };\n" );
  298.         else fprintf( ftable, "," );
  299.         }
  300.     }
  301.  
  302.  
  303. gtnm(){
  304.  
  305.     register s, val, c;
  306.  
  307.     /* read and convert an integer from the standard input */
  308.     /* return the terminating character */
  309.     /* blanks, tabs, and newlines are ignored */
  310.  
  311.     s = 1;
  312.     val = 0;
  313.  
  314.     while( (c=getc(finput)) != EOF ){
  315.         if( isdigit(c) ){
  316.             val = val * 10 + c - '0';
  317.             }
  318.         else if ( c == '-' ) s = -1;
  319.         else break;
  320.         }
  321.  
  322.     *pmem++ = s*val;
  323.     if( pmem > &mem[MEMSIZE] ) error( "out of space" );
  324.     return( c );
  325.  
  326.     }
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.